import math

import itertools

device_name = input('Please enter Device file name:')

# 电池坐标
battery = []

# 其他设备坐标
devices = []

with open(device_name) as f:
    lines = f.readlines()
    # 得到电池坐标
    print(lines[:1])
    battery_points_str = lines[:1][0].replace('\n', '')
    battery_points = battery_points_str.split('-')
    for point in battery_points:
        battery.append(point)
    # 得到设备坐标
    devices_points = lines[1:]
    for point in devices_points:
        devices.append(point.replace('\n', ''))
f.close()

print(battery)
print(devices)


# 2点之间距离方法
def get_instance(point_one, point_two):
    point_one_x_y = point_one.split(',')
    point_two_x_y = point_two.split(',')
    x = int(point_one_x_y[0]) - int(point_two_x_y[0])
    y = int(point_one_x_y[1]) - int(point_two_x_y[1])
    return math.sqrt((x ** 2) + (y ** 2))


# 求集合中的所有的长度之和
def get_all_instance(new_connections):
    sum = 0
    for i in range(len(new_connections)):
        if i == len(new_connections) - 1:
            break
        sum = sum + get_instance(new_connections[i], new_connections[i + 1])
    return sum

# 所有长度的最小值
def get_min_instance(all_possiable_connections):
    min = 10000
    dict = {}
    for possiable_connections in all_possiable_connections:
        instance = get_all_instance(possiable_connections)
        if min > instance:
            min = instance
            dict['conn'] = possiable_connections
            dict['distance'] = min
    return dict


all_min_connections = []

for device in devices:
    all_possiable_connections = []
    # 剩下的Device
    remaind_devices = devices.copy()
    remaind_devices.remove(device)
    # 去掉那一点之后所有的可能组合
    permutations = list((itertools.permutations(remaind_devices, len(remaind_devices))))
    for mid_connections in permutations:
        possiable_connections = []
        # 加上battery起点
        possiable_connections.append(battery[0])
        # 加上中间的所有点
        possiable_connections.extend(list(mid_connections))
        # 加上battery终点
        possiable_connections.append(battery[1])
        # 得到所有可能的组合
        all_possiable_connections.append(possiable_connections)
    all_min_connections.append(get_min_instance(all_possiable_connections))


# 冒泡排序求出最小的长度
def sort_min_cost(all_remove_list):
    for i in range(len(all_remove_list)):
        for j in range(i):
            if all_remove_list[j]['distance'] > all_remove_list[j + 1]['distance']:
                all_remove_list[j], all_remove_list[j + 1] = all_remove_list[j + 1], all_remove_list[j]


sort_min_cost(all_min_connections)

# 得到距离最小的那个
min_conn = all_min_connections[0]

# 拼接打印字符
print_str = ''
for index in range(len(min_conn['conn'])):
    if index > 0:
        print_str = print_str + '->'
    print_str = print_str + '[' + str(min_conn['conn'][index]) + ']'

print('Optimal ', str(round(min_conn['distance'], 2)), 'mm', print_str)

# 2,7-3,7
# 7,0
# 1,1
# 3,4
# 5,1
# 6,4
# 7,5
# 2,5

# 比如去掉7.0 剩下的点能排列出很多种情况，然后我们把很多种情况得到最小值，这个组合就是去掉7.0的组合，和一个最小的距离
# 然后去掉1,1 同理 可得一个组合还有一个距离

# 最后冒泡排序，第一个就是最小的距离，也就是答案的那个结果